import re


def getWord(word, words):
    a = '[a-z]' + word[1] + word[2] + word[3]
    b = word[0] + '[a-z]' + word[2] + word[3]
    c = word[0] + word[1] + '[a-z]' + word[3]
    d = word[0] + word[1] + word[2] + '[a-z]'
    arr = [a, b, c, d]
    for w in words:
        for x in arr:
            if re.match(rf'{x}', w):
                return w
    return None


def mutations(alice, bob, word, first):
    idx = first
    alices = [w for w in alice if len(set(w)) == 4 and w != word]
    bobs = [w for w in bob if len(set(w)) == 4 and w != word]
    players = [alices, bobs]

    def remove_used():
        for player in players:
            while word in player:
                player.remove(word)

    # first turn
    if not getWord(word, players[idx]):
        idx = (idx+1) % 2
        if not getWord(word, players[idx]):
            return -1
        else:
            return idx
    else:
        word = getWord(word, players[idx])
        remove_used()
        idx = (idx+1) % 2
        if not getWord(word, players[idx]):
            return (idx+1) % 2
        else:
            word = getWord(word, players[idx])
            remove_used()
            idx = (idx+1) % 2
    while getWord(word, players[idx]):
        word = getWord(word, players[idx])
        remove_used()
        idx = (idx+1) % 2
    return (idx+1) % 2


alice = ['glob', 'jury', 'elhi', 'dart', 'bass', 'kobo', 'gaed', 'yows', 'hade', 'paca', 'tows', 'jins', 'wack', 'ewes', 'ware', 'yoks', 'frat', 'mads', 'conk', 'boos', 'lief', 'scad', 'mein', 'gold', 'eked', 'logo', 'grum', 'semi', 'gaud', 'cade', 'pulk', 'hack', 'thou', 'glad', 'rhea', 'raft', 'icky', 'ribs', 'omen', 'ilea', 'muon', 'ohed', 'sees', 'holy', 'tips', 'gown', 'hops', 'rhus', 'onos', 'heel', 'swim', 'clon', 'sorn', 'nows', 'biro', 'whom', 'purr', 'kois', 'nurl', 'olla', 'trod', 'rent', 'lope', 'quad', 'giro', 'whig', 'puce', 'hews', 'farm', 'city', 'trog', 'eels', 'dung', 'cued', 'foal', 'yens', 'phon', 'hent', 'quod', 'pail', 'alto', 'kaif', 'deli', 'hued', 'ruer', 'nixe', 'spun', 'tors', 'half', 'whee', 'jays', 'lets', 'wham', 'stum', 'veld', 'geed', 'vacs', 'troy', 'nuns', 'skas',
         'bock', 'rase', 'whew', 'wavy', 'nodi', 'woes', 'time', 'mugg', 'silo', 'rave', 'sots', 'curl', 'gnaw', 'fire', 'bema', 'clew', 'kagu', 'marc', 'suss', 'hora', 'haku', 'hits', 'cops', 'hale', 'lurk', 'data', 'poem', 'pont', 'bobs', 'gate', 'pics', 'gibe', 'oyes', 'zouk', 'slug', 'otto', 'twit', 'whoa', 'rive', 'tofu', 'visa', 'homy', 'zinc', 'psst', 'scow', 'jagg', 'sues', 'tort', 'pans', 'geck', 'acne', 'slob', 'yutz', 'meld', 'mors', 'wept', 'wold', 'meme', 'refs', 'tres', 'cyma', 'rush', 'vita', 'fabs', 'gadi', 'stew', 'here', 'rubs', 'bima', 'shun', 'yams', 'bloc', 'buts', 'deem', 'lums', 'lull', 'cube', 'berk', 'keel', 'bilk', 'puns', 'ripe', 'yelp', 'pies', 'peep', 'revs', 'oleo', 'tone', 'rand', 'fado', 'capo', 'berg', 'caid', 'hoke', 'tens', 'pias', 'tire', 'coxa', 'bags', 'yeti']
bob = ['flam', 'tuff', 'brag', 'maim', 'tire', 'surf', 'came', 'clog', 'oner', 'craw', 'soja', 'pods', 'calm', 'cowl', 'grey', 'jiao', 'pfft', 'ands', 'hype', 'luxe', 'hail', 'bawl', 'yods', 'helm', 'bosk', 'mike', 'egos', 'oped', 'tund', 'ices', 'baff', 'pelf', 'leaf', 'fixt', 'waws', 'unit', 'vims', 'quad', 'snye', 'noel', 'ayin', 'haji', 'woos', 'bien', 'lune', 'tour', 'sent', 'meme', 'maar', 'hant', 'bing', 'luck', 'kobs', 'wavy', 'leys', 'spam', 'amus', 'vier', 'leis', 'unco', 'maut', 'dhak', 'shes', 'beef', 'boys', 'wash', 'just', 'kilt', 'lour', 'yins', 'hypo', 'axed', 'cork', 'gogo', 'pity', 'conk', 'dips', 'doby', 'kuru', 'dais', 'akin', 'koto', 'will', 'alky', 'tiff', 'ogee', 'qoph', 'huns', 'peed', 'agar', 'wiki', 'gens', 'vigs', 'swop', 'pika', 'toys', 'kufi', 'heme', 'pegs', 'silo',
       'fled', 'pean', 'raff', 'ired', 'tide', 'leap', 'wots', 'otto', 'yeuk', 'able', 'wilt', 'fids', 'wits', 'hest', 'bake', 'marl', 'buss', 'they', 'gals', 'dump', 'hade', 'howk', 'togs', 'home', 'roof', 'saki', 'pars', 'tuts', 'coke', 'gets', 'odds', 'mara', 'slim', 'slue', 'skat', 'spur', 'haws', 'hero', 'tips', 'robs', 'mixt', 'tubs', 'dele', 'meta', 'teed', 'wish', 'dune', 'jehu', 'sewn', 'vamp', 'mode', 'corm', 'haft', 'difs', 'lief', 'cake', 'what', 'flux', 'asps', 'swig', 'ills', 'lips', 'vive', 'lobe', 'pang', 'epos', 'cusp', 'otic', 'shun', 'pots', 'thud', 'sift', 'vies', 'juke', 'pehs', 'rime', 'teff', 'gasp', 'sawn', 'anoa', 'maid', 'quiz', 'tods', 'rube', 'dopy', 'awes', 'yeah', 'bits', 'jilt', 'yean', 'pont', 'demo', 'funs', 'etas', 'loco', 'coos', 'soys', 'gory', 'chis', 'undy']

print(mutations(alice, bob, 'cire', 0))
